What is the result of X(X,X)? [closed]

Posted by Sorush Rabiee on Stack Overflow See other posts from Stack Overflow or by Sorush Rabiee
Published on 2010-03-23T13:28:54Z Indexed on 2010/03/23 14:03 UTC
Read the original article Hit count: 345

Filed under:

A friend who studies pure mathematics ask me to think about the following problem.

Suppose that there is an algorithm named X that has 2 inputs: A and a_1...a_n, where 'A' stands for an arbitary algorithm and 'a_1..a_n' are inputs of A. X receives A and its inputs and returns true if A with a_1..a_n could be terminated, and false if A with a_1..a_n inputs fall into an infinite loop (never ends). Like this:

A(n):
   while(n<5):
      write "I'm immortal!"

and the result of X(A,6) is true and X(A,2) is false.

So what is the result of X(X,X)?

Also, do you know who was the first to introduce this problem?

© Stack Overflow or respective owner

Related posts about algorithm